package com;


import java.util.LinkedList;
import java.util.Queue;

/**
 * 在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。
 * <p>
 * 一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, ..., C_k 组成：
 * <p>
 * 相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
 * C_1 位于 (0, 0)（即，值为 grid[0][0]）
 * C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
 * 如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）
 * 返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。
 * 求解有几种路线
 * <p>
 * <p>
 * 思路
 * 类似走迷宫的解法，先找到第 i 步，然后把它周围走一步能到的点的位置都 append 到 list 里。这样就可以得到走 i+1 步的情况下，能走到的所有位置。visited 矩阵初始化全部为 0，然后每次赋值我就把走到这个点需要走几步赋值给它。
 * <p>
 * 如果下一个点就是终点，那就直接返回需要走的 step 就是最短路径的长度了。这个长度肯定是最短的了，因为如果有比它还短的路径，那在之前的搜索过程中就会发现了。
 *
 *  你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
 *
 * 示例 1:
 *
 * 输入: [2,3,2]
 * 输出: 3
 * 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
 * 示例 2:
 *
 * 输入: [1,2,3,1]
 * 输出: 4
 * 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
 *      偷窃到的最高金额 = 1 + 3 = 4 。
 *
 * @author YL
 **/
public class Dynamic1Block {

    private int n = 0;

    /**
     * 8 6 5
     * 7 O 2
     * 4 3 1
     */
    private final int[][] link = new int[][]{
            {1, 1}, {1, 0}, {0, 1},
            {1, -1}, {-1, 1}, {-1, 0},
            {0, -1}, {-1, -1}
    };

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid.length == 0) {
            return -1;
        }

        n = grid.length - 1;
        if (grid[n][n] == 1 || grid[0][0] == 1) {
            // 关门了
            return -1;
        }

        if (n == 0) {
            return 1;
        }

        // 广度优先
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        queue.add(null);
        int path = 1;
        while (!queue.isEmpty()) {
            int[] yx = queue.poll();
            if (yx == null) {
                path ++;
                if (queue.size() != 0) {
                    queue.add(null);
                }
            } else {
                for (int[] ints : link) {
                    int y1 = ints[0] + yx[0];
                    int x1 = ints[1] + yx[1];
                    if (x1 <= n && x1 >= 0 && y1 <= n && y1 >= 0 && grid[y1][x1] == 0) {
                        // 不允许回头找路, 走过的路堵死
                        grid[y1][x1] = 1;
                        queue.add(new int[]{y1, x1});
                    }
                    if (x1 == n && y1 == n) {
                        // 找到退出
                        return path + 1;
                    }
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Dynamic1Block().shortestPathBinaryMatrix(
                new int[][]
                        {
                                {0, 1},
                                {1, 0}
                        }
                        /*
                        {
                                {0, 0, 1, 0, 0, 0, 0},
                                {0, 1, 0, 0, 0, 0, 1},
                                {0, 0, 1, 0, 1, 0, 0},
                                {0, 0, 0, 1, 1, 1, 0},
                                {1, 0, 0, 1, 1, 0, 0},
                                {1, 1, 1, 1, 1, 0, 1},
                                {0, 0, 1, 0, 0, 0, 0}
                        }
                        {
                                {0, 1, 0, 1, 0},
                                {1, 0, 0, 0, 1},
                                {0, 0, 1, 1, 1},
                                {0, 0, 0, 0, 0},
                                {1, 0, 1, 0, 0}
                        }

                        {
                                {0, 0, 0, 0, 1},
                                {1, 0, 0, 0, 0},
                                {0, 1, 0, 1, 0},
                                {0, 0, 0, 1, 1},
                                {0, 0, 0, 1, 0}
                        }*/
        ));
    }
}
